Forma Normal Disyuntiva Principal y Forma Normal Conjuntiva Principal
Estructuras discretas
Departamento de Ingeniería Electrónica

Introducción

Imagina lo siguiente:

El profesor de tu grupo les pide a todos los integrantes que, dada una fórmula proposicional, generen de manera individual una fórmula proposicional equivalente. ¡Te aseguro que todos lo van a lograr!

Ahora imagina que el mismo profesor le pide lo mismo a todos los alumnos de tu escuela: que dada una fórmula proposicional cualquiera, todos generen una fórmula proposicional equivalente. ¡Por supuesto que lo van a lograr!

Pero ahora, ¿qué pasaría si el mismo profesor les pidiera lo mismo, pero que todos llegasen a la misma expresión equivalente, es decir, escrita de la misma manera? ¿Existirá alguna forma de saber que, a partir de una fórmula proposicional cualquiera, todos puedan llegar a encontrar la misma fórmula proposicional equivalente?

Al principio parece una idea un poco descabellada, pero tiene sentido hacer el planteamiento.

En la presente unidad vamos a trabajar con formas normales principales (FNP), sus características y aplicaciones, no sólo en el universo de la lógica, sino en el diseño de circuitos. ¡Interesante!

Objetivo

  • Demostrar que a partir de una fórmula proposicional cualquiera se pueden obtener sus formas normales principales.

Ideas básicas para iniciar

Dada una fórmula proposicional cualquiera, encontremos su forma normal disyuntiva principal (FNDP) y su forma normal conjuntiva principal (FNCP).

Primero aclaremos qué significa cada concepto.
Vamos a hacer uso de las siguientes siglas:
fp: Fórmula proposicional
FNDP: Forma Normal Disyuntiva Principal
FNCP: y su Forma Normal Conjuntiva Principal.

Dada una fp cualquiera se puede obtener la FNDP y la FNCP. Gráficamente.

Para una fórmula proposicional cualquiera se tiene una fórmula equivalente que está formada por disyunciones de mintérminos, denominada forma normal disyuntiva principal FNDP.

¿Qué es un mintérmino?
¿Qué es un maxtérmino?
¿Cuál es la estructura de una FNDP?
¿Cuál es la estructura de una FNCP?

Por otra parte, dadas dos fórmulas proposicionales determinarás si éstas son equivalentes. Una aplicación de las formas normales principales consiste precisamente en ayudar a demostrar la equivalencia entre estas fórmulas. Bien, ¿qué te parece si hacemos un ejemplo?

Con el fin de aclarar las dudas, vamos a presentar un ejemplo muy completo.

Es necesario que tengas a la mano la tabla.


Veamos ahora un ejemplo

Dada la fórmula proposicional
P → Q
Obtener lo siguiente:

Solución:
a) Por medio del método algebraico se obtiene la FNDP
Procedimiento Ley o propiedad
Ahora, se trabaja para llegar a la FNDP
P → Q ⇔ 7P v Q Con-Dis
                ⇔ (7P∧T ) v (Q ∧ T) Identidad
                ⇔ (7P ∧(Qv7Q)) v (Q ∧(P v7P)) Tautología
                ⇔ (7P∧Q) v (7P ∧ 7Q) v (Q ∧ P) v (Q ∧7P) Distributiva
                ⇔ (7P ∧Q) v (7P ∧ 7Q) v (P ∧ Q) v (7P ∧Q) Conmutativa
                ⇔ (7P∧Q) v (7P ∧ 7Q) v (P ∧ Q) Idempotencia
                ⇔ (P ∧ Q) v (7P ∧Q) v (7P ∧ 7Q)   FNDP Conmutativa
b: Por medio del método algebraico se obtiene la FNCP
Procedimiento Ley o propiedad
Obtener la FNCP
P → Q ⇔ (7P v Q)    FNCP Con-Dis
c: A partir de la FNDP obtener la FNCP
Procedimiento Ley o propiedad
Ahora, se llega a la FNCP
 
P → Q ⇔ (P ∧ Q) v (7P ∧ Q) v (7P ∧ 7Q) trabaja con ella. Con-Dis
 
(P ∧ Q) v (7P ∧ Q) v (7P ∧ 7Q)⇔(P ∧ Q) v (7P ∧ (Q v 7Q)) Distributiva
                     ⇔(P ∧ Q) v (7P ∧ ( T     )) Tautología
                    ⇔ (P ∧ Q) v (    7P       ) Identidad
                    ⇔ (P v 7P) ∧ (Q v 7P) Distributiva
                    ⇔ ( T ) ∧(7P v Q) Tautología y conm.
                    ⇔ 7P v Q       FNCP Identidad
d: A partir de la FNCP obtener la FNDP
Procedimiento Ley o propiedad
Ahora, se llega a la FNDP
 
P → Q ⇔(7P v Q) ésta es la FNCP, trabaja con ella. Con-Dis
 
(7P v Q) ⇔ (7P ∧ T) v (Q ∧ T) Identidad
                   ⇔ (7P ∧(Q v 7Q)) v (Q ∧ (P v 7P)) Tautología
                  ⇔ (7P ∧Q) v (7P ∧ 7Q) v (Q ∧ P) v (Q ∧ 7P) Distributiva
                  ⇔ (7P ∧ Q) v (7P ∧ 7Q) v (P ∧ Q) v (7P ∧ Q) Conmutativa
                  ⇔ (7P ∧ Q) v (7P ∧ 7Q) v (P ∧ Q) Idempotencia
                  ⇔ (P ∧ Q) v (7P ∧ Q) v (7P ∧ 7Q)       FNDP Conmutativa
e: Obtén ahora las formas normales principales por el método de tablas de verdad.
Otra forma de resolver el problema consiste en el uso de la tabla de verdad.
Se construye la tabla de verdad de la fórmula dada.


P   Q P → Q
T   T T
T   F F
F   T T
F   F T

De acuerdo con la tabla de verdad, se observa que la fórmula original, P → Q es una contingencia. Por lo tanto, tiene las dos formas normales principales: FNDP y FNCP.

Para obtener la FNDP a partir de la tabla de verdad, trabaja con los renglones que tienen valor verdadero en la columna resultante y genera las combinaciones directamente. Cada combinación es un mintérmino. El único conectivo binario que contiene cada mintérmino corresponde a la conjunción.



P   Q P → Q FNDP FNCP
T   T T (P ∧ Q)  
T   F F    
F   T T (7P ∧ Q)  
F   F T (7P ∧ 7Q)  


Finalmente, relaciona los mintérminos obtenidos por medio de disyunciones.

Así, la FNDP está dada por:

    (P ∧ Q) v (7P ∧ Q) v (7P ∧ 7Q)

Se cumple la equivalencia:

   P → Q ⇔ (P ∧Q) v (7P ∧ Q) v (7P ∧ 7Q)

Por otra parte, para obtener la FNCP a partir de la tabla de verdad, trabaja con los renglones que tienen valor falso en la columna resultante. Para generar las combinaciones correspondientes observa el valor de la atómica y cámbialo. Si es verdadero niégalo (7). Si es falso conviértelo en verdadero.

Cada combinación obtenida es un maxtérmino. El único conectivo binario que contiene cada maxtérmino corresponde a la disyunción. Si existe más de un maxtérmino, relaciónalos por medio de conjunciones.



P   Q P → Q FNDP FNCP
T   T T (P ∧ Q)  
T   F F   (7P v Q)
F   T T (7P ∧ Q)  
F   F T (7P ∧ 7Q)  


De la tabla, obtenemos sólo un maxtérmino, por lo que no se necesitan conjunciones para relacionarlo.

Así, la FNCP está dada por:

   (7P v Q)

Se cumple la equivalencia:

   P → Q ⇔ (7P v Q)



Comentarios:

Se llama forma normal principal porque cada término contiene a todas las atómicas que aparecen en la fórmula original. La forma normal principal toma el nombre del conectivo que relaciona a los términos. Así, en el caso de los mintérminos, éstos se relacionan con disyunciones, por eso se llama forma normal disyuntiva principal, FNDP. Para el caso de los maxtérminos, éstos se relacionan con conjunciones, de ahí el nombre de forma normal conjuntiva principal, FNCP. Otro punto muy importante es que las formas normales principales son únicas. Como ves, existen diferentes modalidades para obtener las formas normales principales.

Si la fórmula original es una contingencia entonces contiene FNDP y FNCP.
Si la fórmula original es una tautología entonces contiene únicamente FNDP.
Si la fórmula original es una contradicción entonces contiene únicamente FNCP.

La suma de términos de la FNDP ( # t FNDP ) y de la FNCP ( # t FNCP ) es igual a 2n, donde n es el número de atómicas que contiene la fórmula original.


     # t FNDP + # t FNCP=2n


Para el ejercicio, n = 2


     # t FNDP + # t FNCP=3 + 1=22=4


Recuerda, las formas normales principales cumplen tres condiciones:
1. El único conectivo que se permite usar fuera de los términos corresponde al nombre de la forma normal principal. El conectivo aparece cuando existe más de un término.
2. El único conectivo binario que se permite dentro de cada término es el dual del conectivo externo.
3. Dentro de cada término deben aparecer todas las atómicas (sin ser negadas, pero no ambas) que contiene la fórmula proposicional original.

Observa que en las formas normales principales, los únicos conectivos que pueden aparecer son v, ∧ y 7.

La forma normal disyuntiva principal, FNDP, también tiene el nombre de forma canónica de suma de productos.

A la forma normal conjuntiva principal, FNCP, también se le conoce como la forma canónica de producto de sumas.

¿Qué te pareció el método usando tablas de verdad? A primera vista parece más sencillo. Sin embargo, te recomiendo que domines el método algebraico y el método por tablas de verdad te puede servir para comprobar tus resultados.

Veamos otro ejemplo

Obtener las formas normales principales de la siguiente fórmula proposicional:

    P v (7P ∧ Q)

Solución:
a: Por medio del método algebraico se obtiene la FNDP
Procedimiento Ley o propiedad
 
P v (7P ∧ Q) ⇔ (P ∧ T) v (7P ∧Q) Identidad
                          ⇔ (P ∧ (Qv7Q)) v (7P ∧Q) Tautología
                          ⇔ (P ∧ Q) v (P ∧ 7Q) v (7P ∧ Q)      FNDP Distributiva
b: Por medio del método algebraico se obtiene la FNCP
Procedimiento Ley o propiedad
 
P v (7P ∧ Q) ⇔ (P v 7P) ∧ (P v Q) Distributiva
                          ⇔ (T ) ∧ (P v Q) Tautología
                          ⇔ (P v Q)    FNCP Identidad
c: Obtener las formas normales principales por el método de tablas de verdad.
Otra forma de resolver el problema consiste en el uso de la tabla de verdad. Se construye la tabla de verdad de la fórmula dada.


P   Q P v (7P ∧ Q)
T   T T
T   F T
F   T T
F   F F


De acuerdo con la tabla de verdad, se observa que la fórmula original, P v (7P ∧ Q) es una contingencia. Por lo tanto, tiene las dos formas normales principales: FNDP y FNCP.

Para obtener la FNDP a partir de la tabla de verdad, trabaja con los renglones que tienen valor verdadero en la columna resultante y escribe las combinaciones directamente. Cada combinación corresponde a un mintérmino, el cual contiene conjunciones y, en su caso, negaciones.



P   Q P v (7P ∧ Q) FNDP FNCP
T   T T (P ∧ Q)  
T   F T (P ∧ 7Q)
F   T T (7P ∧ Q)
F   F F


Finalmente, relaciona lo obtenido con disyunciones.

Entonces la FNDP está dada por:

    (P ∧ Q) v (P ∧ 7Q) v (7P ∧ Q)

Se cumple la equivalencia:

    P v (7P ∧ Q) ⇔ (P ∧ Q) v (P ∧ 7Q) v (7P ∧ Q)

Por otra parte, para obtener la FNCP a partir de la tabla de verdad, trabaja con los renglones que tienen valor falso en la columna resultante. Para escribir las combinaciones correspondientes observa el valor de la atómica y cámbialo.

Cada combinación corresponde a un maxtérmino, el cual contiene disyunciones y, en su caso, negaciones.



P   Q P v (7P ∧ Q) FNDP FNCP
T   T T (P ∧ Q)  
T   F T (P ∧ 7Q)
F   T T (7P ∧ Q)
F   F F (P v Q)


Relaciona lo obtenido por medio de conjunciones, si existe más de un maxtérmino. En este ejercicio sólo existe un maxtérmino.

Entonces la FNCP está dada por:

    (P v Q)

Se cumple la equivalencia:

    P v (7P ∧ Q) ⇔ (P v Q)

Para la solución “d” y “e”, hacemos uso de la tabla obtenida en la solución “c”.
d: A partir de los términos faltantes de la FNDP se obtiene la FNCP.
Procedimiento
Ya se obtuvo la FNDP
P v (7P ∧ Q) ⇔ (P ∧ Q) v (P ∧ 7Q) v(7P ∧ Q)      FNDP
Ahora, a partir de la FNDP se obtiene la otra forma, ¿cómo?
Observa la tabla de verdad:
Primero: Los términos (las combinaciones) faltantes de la FNDP son
(7P ∧ 7Q)
Segundo: Relaciona los términos faltantes con v. Como sólo es uno, no es necesario.
(7P ∧ 7Q) Se deja igual
Tercero: Encierra lo obtenido entre paréntesis cuadrados y niégalo:
7[(7P ∧ 7Q)]
Cuarto: Aplica la ley de Morgan y desarrolla:
7[(7P ∧ 7Q)]⇔ 77P v 77Q
⇔ (P v Q)    FNCP
e: A partir de los términos faltantes de la FNCP se obtiene la FNDP.
Procedimiento
Ya se obtuvo la FNCP
P v (7P ∧ Q) ⇔ (P v Q)    FNCP
Ahora, a partir de la FNCP se obtiene la otra forma, ¿cómo?
Observa la tabla de verdad:
Primero: Los términos (las combinaciones) faltantes de la FNCP son:
(P v 7Q), (7P v Q) y (7P v 7Q)
Segundo: Relaciona los términos faltantes con ∧:
(P v 7Q) ∧ (7P v Q) ∧ (7P v 7Q)
Tercero: Encierra lo obtenido entre paréntesis cuadrados y niégalo:
7[(P v 7Q) ∧ (7P v Q) ∧ (7P v 7Q)]
Cuarto: Aplica la ley de Morgan y desarrolla:
7[(P v 7Q) ∧ (7P v Q) ∧ (7P v 7Q)] ⇔ 7(P v 7Q) v 7 (7P v Q) v 7(7P v 7Q)
                                ⇔ (7P ∧ Q) v (P ∧ 7Q) v (P ∧ Q)
                               ⇔ (P ∧ Q) v (P ∧ 7Q) v (7P ∧ Q) FNDP
Comentarios:

Se llama forma normal principal porque cada término contiene a todas las atómicas que aparecen en la fórmula original. La forma normal principal toma el nombre del conectivo que relaciona a los términos. Así, en el caso de los mintérminos, éstos se relacionan con disyunciones, por eso se llama forma normal disyuntiva principal, FNDP.

Para el caso de los maxtérminos, éstos se relacionan con conjunciones, de ahí el nombre de forma normal conjuntiva principal, FNCP. Otro punto muy importante es que las formas normales principales son únicas. Como ves, existen diferentes modalidades para obtener las formas normales principales. Ahora, practica:

Si la fórmula original es una contingencia entonces contiene FNDP y FNCP. La suma de términos de la FNDP ( # t FNDP ) y de la FNCP ( # t FNCP ) es igual a 2n, donde n es el número de atómicas que contiene la fórmula.

        # t FNDP + # t FNCP=2n

Para el ejercicio, n=2

       # t FNDP + # t FNCP=3 + 1=22=4

Recuerda, las formas normales principales cumplen tres condiciones:
1. El único conectivo que se permite usar fuera de los términos corresponde al nombre de la forma normal principal. El conectivo aparece cuando existe más de un término.
2. El único conectivo binario que se permite dentro de cada término es el dual del conectivo externo.
3. Dentro de cada término deben aparecer todas las atómicas (sin ser negadas, pero no ambas) que contiene la fórmula proposicional original

Observa que en las formas normales principales, los únicos conectivos que pueden aparecer son v, ∧ y 7.

La forma normal disyuntiva principal, FNDP, también tiene el nombre de forma canónica de suma de productos.

A la forma normal conjuntiva principal, FNCP, también se le conoce como la forma canónica de producto de sumas.

Si te introduces al mundo del álgebra booleana, la notación cambia. Así, para el ejemplo que acabas de terminar, su notación queda de la siguiente manera:

Forma canónica de suma de productos:
p + p’q=pq + pq’ + p’q

Forma canónica de producto de sumas:
p + p’q=(p+q)

Actividad 1. La prueba de fuego

Muy bien. Es el momento de usar el proceso para encontrar las formas normales principales: FNDP y FNCP. Recuerda que vamos a usar el método algebraico. Se te indicará la propiedad que se está utilizando. Con mucho cuidado selecciona la expresión correcta. Si tienes alguna duda, consulta la tabla II. ¿Estás listo? ¡Iniciamos!

Autoevaluación 1. ¡Tú puedes con todo!

Ha llegado el momento de demostrar que dominas los conceptos de las formas normales principales. Completa las oraciones arrastrando las opciones del lado derecho a los espacios correspondientes. Al finalizar podrás conocer tu desempeño. ¿Estás listo? ¡Adelante!

Fuentes de información

Bibliografía

Epp, S. (2012). Matemáticas discretas con aplicaciones (4.a ed.). México: Cengage Learning.

Kolman, B. (2009). Discrete mathematical structures [Estructuras matemáticas discretas] (6th.). New Jersey: Pearson/Prentice Hall

Tremblay, J. y Manohar, R. (1996). Matemáticas discretas. Con aplicación a las ciencias de la computación (R. Rangel trad.). México: Continental.

Veerarajan, T. (2008). Matemáticas discretas. Con teoría de gráficas y combinatoria. México: McGraw-Hill.

Zaldívar E. O. y Zaldívar, O. (2014). Estructuras discretas. Lógica proposicional y cálculo de predicados. Cuaderno de ejercicios (2.ª ed.). México: UNAM.

 

Dado un número de proposiciones atómicas o variables, el mintérmino consiste en conjunciones donde aparecen todas las atómicas o variables o su negación, pero no ambas.

Entonces, para una fórmula proposicional cualquiera, se tiene una fórmula equivalente que está formada por conjunciones de maxtérminos, ésta es denominada forma normal conjuntiva principal FNCP.

Dado un número de proposiciones atómicas o variables, el maxtérmino consiste en disyunciones donde aparecen todas las atómicas o variables o su negación, pero no ambas.

Si analizamos estas definiciones entonces podemos decir que los mintérminos son los duales de los maxtérminos.

Suponemos que ya llegaste a la conclusión de que los únicos conectivos que pueden aparecer en las formas normales principales son la conjunción (∧), la disyunción (v) y la negación (7).

La estructura de una FNDP es la siguiente: Primero: el único conectivo binario que puede aparecer fuera de los paréntesis es la disyunción (de ahí toma su nombre “disyuntiva”). Cada paréntesis corresponde a un mintérmino. ( ) v ( ) v ( ) v ….. v ( )

Segundo: el único conectivo binario que puede aparecer dentro de los paréntesis es la conjunción, es decir, el dual de la disyunción. ( ∧ ) v ( ∧ ) v ( ∧ ) v ….. v ( ∧ )

Tercero: dentro de los paréntesis puede aparecer o no el conectivo de negación (7). ( ∧, 7 ) v ( ∧, 7 ) v ( ∧, 7 ) v ….. v ( ∧, 7 )

Cuarto: para que la forma normal adquiera la categoría de principal debe contener en cada mintérmino a todas las atómicas o variables (negadas o sin negar, pero no ambas), que aparezcan en la fp original. ( ∧, 7, todas las atómicas) v ( ∧, 7, todas las atómicas ) v ( ∧, 7, todas las atómicas) v ….. v ( ∧, 7, todas las atómicas)

La estructura de una FNCP es la siguiente: Primero: el único conectivo binario que puede aparecer fuera de los paréntesis es la conjunción (de ahí toma su nombre “conjuntiva”). Cada paréntesis corresponde a un maxtérmino. ( ) ∧ ( ) ∧ ( ) ∧ ….. ∧ ( )

Segundo: el único conectivo binario que puede aparecer dentro de los paréntesis es la disyunción, es decir, el dual de la conjunción. ( v ) ∧ ( v ) ∧ ( v ) ∧ ….. ∧ ( v )

Tercero: dentro de los paréntesis puede aparecer o no el conectivo de negación (7). ( v, 7 ) ∧ ( v, 7 ) ∧ ( v, 7 ) ∧ ….. ∧ ( v, 7 )

Cuarto: para que la forma normal adquiera la categoría de principal debe contener en cada maxtérmino a todas las atómicas o variables (negadas o sin negar, pero no ambas) que aparezcan en la fp original.

( v, 7, todas las atómicas) ∧ ( v, 7, todas las atómicas ) ∧ ( v, 7, todas las atómicas) ∧ ….. ∧ ( v, 7, todas las atómicas)